题解 CF1085D Minimum Diameter Tree

发表于 | 更新于

题意:给你一棵$N$个点的树，和一个正整数$s$。

现在让你在这棵树上给$N-1$条边分配边权，使得这棵树的直径最小。

输出最小的直径。

保证$2\leqslant n\leqslant 100000,1\leqslant s\leqslant10^9$。

你的答案是正确的当且仅当与标准答案的绝对误差或相对误差不超过$10^{-6}$。

树的直径的两个端点一定是叶子节点(当边权都为正时)，这个结论显然；

将每一条边分成两类，一类为叶子节点连接的边，设为$a$，另一类为没有叶子节点连接的边，设为$b$；

对于$b$，我们希望每条$b$对直径贡献尽量小，因为两条可能成为直径的边可能同时包含了$b$。所以将所有$b$的值设为$0$；

根据这个结论，我们将所有$s$均摊给每条$a$；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
#define ll long long
using namespace std;
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
int cnt,r[300000];
int main(){
    int n=read(),m=read();
    for (int i=1;i<n;++i){
        int u=read(),v=read();
        ++r[u];++r[v];
    }
    for (int i=1;i<=n;++i)
        if (r[i]==1)
            ++cnt;
    printf("%.18lf",2*m*1.0/(cnt*1.0));
}